package arithmetic.leetCode.yi;

import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: yilin
 * Date: 2019-08-07 Time: 17:56
 */
public class TreeToLinkList {

    public class TreeNode {

        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public class ListNode {

        int val;
        ListNode left;
        ListNode right;

        ListNode(int x) {
            val = x;
        }
    }

    public TreeNode ConvertWithStack(TreeNode pRootOfTree) {
        if (pRootOfTree == null) {
            return null;
        }

        // 当前节点
        TreeNode cur = pRootOfTree;
        // 用于指向当前节点的前一个节点，开始时为 null。
        TreeNode pre = null;

        Stack<TreeNode> stack = new Stack<TreeNode>();

        while (!stack.isEmpty() || cur != null) {

            // 左子树节点入栈
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            if (pre == null) {
                // 刚开始的时候 pre==null 将最左边的 节点赋值给 pRootOfTree。当前节点复值给pre
                pre = cur;
                pRootOfTree = cur;
            } else {
                pre.right = cur;
                cur.left = pre;
                pre = cur;
            }
            cur = cur.right;

        }

        return pRootOfTree;
    }
}
